<?php
// 找到全排序的下一个数, 又叫"字典序算法"

class FullSortNextNumber {

    /**
     * 寻找数字置换的边界
     * @param array $numbers
     * @return int
     */
    private function findTransferPoint(array $numbers): int {
        for ($i = count($numbers) - 1; $i > 0; $i--) {
            if ($numbers[$i] > $numbers[$i - 1]) {
                return $i;
            }
        }
        return 0;
    }

    /**
     * 交换边界: 把小数放到前面
     * @param array $numbers
     * @param int $index
     * @return array
     */
    private function exchangeHead(array $numbers, int $index) {
        $head = $numbers[$index - 1];
        for ($i = count($numbers) - 1; $i > 0; $i--) {
            if ($head < $numbers[$i]) {
                $numbers[$index - 1] = $numbers[$i];
                $numbers[$i] = $head;
                break;
            }
        }

        return $numbers;
    }

    /**
     * 逆序转顺序
     * @param array $num
     * @param int $index
     * @return array
     */
    private function reverse(array $num, int $index): array {
        for ($i = $index, $j = count($num) - 1; $i < $j; $i++, $j--) {
            $t = $num[$i];
            $num[$i] = $num[$j];
            $num[$j] = $t;
        }
        return $num;
    }

    /**
     * @param array $numbers
     * @return array|null
     */
    private function findNearestNumber(array $numbers) {
        //1. 从后向前查看逆序区域, 找到逆序区域的前一位, 也就是数字置换的边界
        $index = $this->findTransferPoint($numbers);
        //如果数字置换边界是0, 说明整个数组已经逆序,无法得到更大的相同数字组成的整数, 返回null
        if ($index === 0) {
            return null;
        }

        //2. 把逆序区域的前一位和逆序区域中刚刚大于它的数字交换位置
        $numbers = $this->exchangeHead($numbers, $index);

        //3. 把原来的逆序区域转为顺序
        $numbers = $this->reverse($numbers, $index);

        return $numbers;
    }

    public function do() {
        $numbers = [1, 2, 3, 4, 5];
        //打印12345之后的10个全排列整数
        for ($i = 0; $i < 10; $i++) {
            $numbers = $this->findNearestNumber($numbers);
            echo implode('', $numbers) . PHP_EOL;
        }
    }

}

$m = new FullSortNextNumber();
$m->do();